
##def CROSS(dest,v1,v2):
##               dest[0]=v1[1]*v2[2]-v1[2]*v2[1]
##               dest[1]=v1[2]*v2[0]-v1[0]*v2[2]
##               dest[2]=v1[0]*v2[1]-v1[1]*v2[0]
##
##def DOT(v1,v2):
##    return v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2]
## 
##
##
##def SUB(dest,v1,v2):
##    dest[0]=v1[0]-v2[0]
##    dest[1]=v1[1]-v2[1]
##    dest[2]=v1[2]-v2[2] 
##
##
##def SCALAR(dest,alpha,v):
##    dest[0] = alpha * v[0]
##    dest[1] = alpha * v[1]
##    dest[2] = alpha * v[2]
##
##
##
##def CHECK_MIN_MAX(p1,q1,r1,p2,q2,r2) :
##  SUB(v1,p2,q1)
##  SUB(v2,p1,q1)
##  CROSS(N1,v1,v2)
##  SUB(v1,q2,q1)
##  if DOT(v1,N1) > 0.0:
##    return 0
##  SUB(v1,p2,p1)
##  SUB(v2,r1,p1)
##  CROSS(N1,v1,v2)
##  SUB(v1,r2,p1)
##  if DOT(v1,N1) > 0.0:
##    return 0
##  return 1

def ORIENT_2D(a, b, c):
    return (a[0]-c[0])*(b[1]-c[1])-(a[1]-c[1])*(b[0]-c[0])


def INTERSECTION_TEST_VERTEX(P1, Q1, R1, P2, Q2, R2) : 
    if ORIENT_2D(R2,P2,Q1) >= 0.0:
        if ORIENT_2D(R2,Q2,Q1) <= 0.:
            if (ORIENT_2D(P1,P2,Q1) > 0.) :
                if (ORIENT_2D(P1,Q2,Q1) <= 0.) :
                    return 1 
                else:
                    return 0
            else :
                if (ORIENT_2D(P1,P2,R1) >= 0.):
                    if (ORIENT_2D(Q1,R1,P2) >= 0.):
                        return 1 
                    else :
                        return 0
                else :
                    return 0
        else :
            if (ORIENT_2D(P1,Q2,Q1) <= 0.):
                if (ORIENT_2D(R2,Q2,R1) <= 0.):
                    if (ORIENT_2D(Q1,R1,Q2) >= 0.):
                        return 1 
                    else :
                        return 0
                else :
                    return 0
            else :
                return 0
    else :
        if (ORIENT_2D(R2,P2,R1) >= 0.) :
            if (ORIENT_2D(Q1,R1,R2) >= 0.) :
                if (ORIENT_2D(P1,P2,R1) >= 0.):
                    return 1
                else :
                    return 0
            else :
                if (ORIENT_2D(Q1,R1,Q2) >= 0.) :
                    if (ORIENT_2D(R2,R1,Q2) >= 0.):
                        return 1 
                    else:
                        return 0
                else:
                    return 0 
        else :
            return 0 



def INTERSECTION_TEST_EDGE(P1, Q1, R1, P2, Q2, R2) :
    if (ORIENT_2D(R2,P2,Q1) >= 0.) :
        if (ORIENT_2D(P1,P2,Q1) >= 0.)  :
            if (ORIENT_2D(P1,Q1,R2) >= 0.):
                return 1 
            else :
                return 0
        else :
            if (ORIENT_2D(Q1,R1,P2) >= 0.) :
                if (ORIENT_2D(R1,P1,P2) >= 0.):
                    return 1
                else :
                    return 0
            else :
                return 0
    else :
        if (ORIENT_2D(R2,P2,R1) >= 0.) :
            if (ORIENT_2D(P1,P2,R1) >= 0.) :
                if (ORIENT_2D(P1,R1,R2) >= 0.):
                    return 1  
                else :
                    if (ORIENT_2D(Q1,R1,R2) >= 0.):
                        return 1
                    else:
                        return 0
            else:
                return 0
        else :
            return 0


#def ccw_tri_tri_intersection_2d(float p1[2], float q1[2], float r1[2], 

def ccw_tri_tri_intersection_2d( p1,  q1,  r1, p2,  q2,  r2) :
    if ( ORIENT_2D(p2,q2,p1) >= 0. ):
        if ( ORIENT_2D(q2,r2,p1) >= 0. ) :
            if ( ORIENT_2D(r2,p2,p1) >= 0. ):
                return 1
            else :
                return INTERSECTION_TEST_EDGE(p1,q1,r1,p2,q2,r2)
        else :
            if ( ORIENT_2D(r2,p2,p1) >= 0. ) :
                return INTERSECTION_TEST_EDGE(p1,q1,r1,r2,p2,q2)
            else :
                return INTERSECTION_TEST_VERTEX(p1,q1,r1,p2,q2,r2)
    else :
        if ( ORIENT_2D(q2,r2,p1) >= 0. ) :
            if ( ORIENT_2D(r2,p2,p1) >= 0. ) :
                return INTERSECTION_TEST_EDGE(p1,q1,r1,q2,r2,p2)
            else :
                return INTERSECTION_TEST_VERTEX(p1,q1,r1,q2,r2,p2)
        else :
            return INTERSECTION_TEST_VERTEX(p1,q1,r1,r2,p2,q2)


def tri_tri_overlap_test_2d( p1,  q1,  r1, p2,  q2,  r2) :
    if ( ORIENT_2D(p1,q1,r1) < 0. ):
        if ( ORIENT_2D(p2,q2,r2) < 0. ):
            return ccw_tri_tri_intersection_2d(p1,r1,q1,p2,r2,q2)
        else:
            return ccw_tri_tri_intersection_2d(p1,r1,q1,p2,q2,r2)
    else:
        if ( ORIENT_2D(p2,q2,r2) < 0. ) :
            return ccw_tri_tri_intersection_2d(p1,q1,r1,p2,r2,q2)
        else :
            return ccw_tri_tri_intersection_2d(p1,q1,r1,p2,q2,r2)

if __name__=="__main__":
    A1=[0,0]
    A2=[1,0]
    A3=[1,1]
    
    B1=[0.5,0.5]
    B2=[4,0]
    B3=[4,5]
    
    print tri_tri_overlap_test_2d( A1,A2,A3,B1,B2,B3) 
    
    import fast_geom as fg
    
    print fg.triangleOverlapTest( (A1,A2,A3),(B1,B2,B3))
    
 